"""
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，
并将这些区域里所有的 'O' 用 'X' 填充。
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "O", "X", "X"]
示例 1：

    ["X", "X", "X", "X"],                     ["X", "X", "X", "X"],
    ["X", "O", "O", "X"],     ---->           ["X", "X", "X", "X"],
    ["X", "X", "O", "X"],                     ["X", "X", "X", "X"],
    ["X", "O", "X", "X"]                      ["X", "O", "X", "X"]
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。
任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，
则称它们是“相连”的。

示例 2：
输入：board = [["X"]]
输出：[["X"]]

链接：https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from mode import *

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        ["X", "X", "X", "X"],  找到再边界与O连通的点    ["X", "X", "X", "X"],       把O变成X
        ["X", "O", "O", "X"],     将其变成B           ["X", "X", "X", "X"],    ------------->
        ["X", "X", "O", "X"],     ----------->       ["X", "X", "X", "X"],
        ["X", "O", "X", "X"]                         ["X", "B", "X", "X"]

        ["X", "X", "X", "X"],        把B变成O         ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],      ---------->       ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],                        ["X", "X", "X", "X"],
        ["X", "B", "X", "X"]                         ["X", "O", "X", "X"]
        """
        if not board or not board[0]:
            return
        row = len(board)
        col = len(board[0])

        def bfs(i, j):
            deque = collections.deque()
            deque.appendleft((i, j))
            while deque:
                i, j = deque.pop()
                if 0 <= i < row and 0 <= j < col and board[i][j] == "O":
                    board[i][j] = "B"
                    for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        deque.appendleft((i + x, j + y))

        for j in range(col):
            # 第一行
            if board[0][j] == "O":
                bfs(0, j)
            # 最后一行
            if board[row - 1][j] == "O":
                bfs(row - 1, j)
        print(board)

        for i in range(row):
            if board[i][0] == "O":
                # 第一列
                bfs(i, 0)
            if board[i][col - 1] == "O":
                # 最后一列
                bfs(i, col - 1)
        print(board)
        for i in range(row):
            for j in range(col):
                if board[i][j] == "O":
                    board[i][j] = "X"
                if board[i][j] == "B":
                    board[i][j] = "O"

        print(board)


class Solution1:
    def solve(self, board: List[List[str]]) -> None:
        row, col = len(board), len(board[0])

        def bfs(i, j):
            deque = collections.deque()
            deque.append((i, j))
            while deque:
                i, j = deque.pop()
                while 0 <= i < row and 0 <= j < col and board[i][j] == 'O':
                    board[i][j] = 'B'
                    for (x, y) in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                        deque.append([i + x, j + y])
                        print(x, y)

        for j in range(col):
            if board[0][j] == 'O':
                bfs(0, j)
            if board[row - 1][j] == 'O':
                bfs(row - 1, j)

        for i in range(row):
            if board[i][0] == 'O':
                bfs(i, 0)
            if board[i][col - 1] == 'O':
                bfs(i, col - 1)

        for i in range(row):
            for j in range(col):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                if board[i][j] == 'B':
                    board[i][j] = 'O'

        print(board)


if __name__ == "__main__":
    a = [
        ["X", "X", "X", "X"],
        ["X", "O", "O", "X"],
        ["X", "X", "O", "X"],
        ["X", "O", "X", "X"]
    ]
    res = [
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "X", "X", "X"],
        ["X", "O", "X", "X"]
    ]
    # A = Solution()
    # print(A.solve(a))
    A = Solution1()
    print(A.solve(a))
